package hash;

import java.util.*;

/**
 * 49. 字母异位词分组
 * 中等
 * 相关标签
 * 相关企业
 * 给你一个字符串数组，请你将 字母异位词 组合在一起。可以按任意顺序返回结果列表。
 * <p>
 * 字母异位词 是由重新排列源单词的所有字母得到的一个新单词。
 * <p>
 * 示例 1:
 * <p>
 * 输入: strs = ["eat", "tea", "tan", "ate", "nat", "bat"]
 * 输出: [["bat"],["nat","tan"],["ate","eat","tea"]]
 * 示例 2:
 * <p>
 * 输入: strs = [""]
 * 输出: [[""]]
 * 示例 3:
 * <p>
 * 输入: strs = ["a"]
 * 输出: [["a"]]
 * <p>
 * <p>
 * 提示：
 * <p>
 * 1 <= strs.length <= 104
 * 0 <= strs[i].length <= 100
 * strs[i] 仅包含小写字母
 */
public class GroupAnagrams_49 {
    public static void main(String[] args) {
        String[] strs = {"eat", "tea", "tan", "ate", "nat", "bat"};
        System.err.println(groupAnagrams_1(strs));
        System.err.println(groupAnagrams_2(strs));
    }

    //哈希表计数统计
    public static List<List<String>> groupAnagrams_1(String[] strs) {
        Map<Map<Character, Integer>, List<String>> mapListHashMap = new HashMap<>();
        System.err.println(strs.length);
        for (int i = strs.length - 1; i >= 0; i--) {
            char[] chars = strs[i].toCharArray();
            HashMap<Character, Integer> map = new HashMap<>();
            for (char aChar : chars) {
                map.put(aChar, map.getOrDefault(aChar, 0) + 1);
            }
            List<String> orDefault = mapListHashMap.getOrDefault(map, new ArrayList<>());
            orDefault.add(strs[i]);
            mapListHashMap.put(map, orDefault);
        }
        return new ArrayList<>(mapListHashMap.values());
    }

    public static List<List<String>> groupAnagrams_2(String[] strs) {
        HashMap<String, List<String>> map = new HashMap<>();
        for (String str : strs) {
            char[] chars = str.toCharArray();
            Arrays.sort(chars);
            String s = new String(chars);
            List<String> ans = map.getOrDefault(s, new ArrayList<String>());
            ans.add(str);
            map.put(s, ans);
        }
        return new ArrayList<>(map.values());
    }
}
